//
// Created by LH on 2017/9/7.
//要注意邻接表head和next数组储存的数据仅仅用于索引，图节点数据要去访问map数组

#include <iostream>
using namespace std;

int map[50][3];
int head[100];
int nx[100];
int book[100];
int dis[100];
int n, m,start;

inline int mtos(int min_i, int si)  //计算一点到另一点的距离
{
    int s = head[min_i];	//search
    while (s!=-1)
    {
        if (map[s][1]==si)
        {
            return map[s][2];
        }
        s = nx[s];
    }
    return 1e9;
}

int main()
{
    cin >> n >> m >> start;
    for (int t_init=0;t_init<=n;t_init++)//初始化head和dis
    {
        head[t_init] = -1;
        dis[t_init] = 1e9;
    }

    dis[start] = 0;
    for (int t_input=1;t_input<=m;t_input++)    //构造邻接表
    {
        int t1, t2, t3;
        cin >> t1 >> t2 >> t3;
        map[t_input][0] = t1;
        map[t_input][1] = t2;
        map[t_input][2] = t3;
        nx[t_input] = head[t1];
        head[t1] = t_input;
    }
    book[0] = 1;
    book[start] = 1;

    int sk = head[start];	//search start初始化dis
    while (sk!=-1)
    {
        dis[map[sk][1]] = mtos(start,map[sk][1]);
        sk = nx[sk];
    }

    for (int pro = 1; pro <=n; pro++)
    {
        int min_l = 1e9, min_i = 0;
        for (int t_sh = 1; t_sh <=n; t_sh++)    //查找当前可用权值最小的节点作为搜索起点
        {
            if (!book[t_sh]&&dis[t_sh]<min_l)
            {
                min_l = dis[t_sh];
                min_i = t_sh;
            }
        }

        book[min_i] = 1;
        int si = head[min_i];	//start index
        while (si!=-1&&!book[si])   //搜索、替换
        {
            int ms = mtos(min_i, map[si][1]);
            if (dis[min_i]+ms<dis[map[si][1]])
            {
                dis[map[si][1]] = dis[min_i] + ms;
            }
            si = nx[si];
        }
    }

    for (int t_pnt = 1; t_pnt <= n; t_pnt++)
    {
        cout << dis[t_pnt] << " ";
    }
    cout << endl;

    return 0;
}

/*
6 9 1
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 12
4 6 15
5 6 4
 * */